// FIT_6204_Gorodilov_TrSegDoc.cpp : implementation of the CFIT_6204_Gorodilov_TrSegDoc class
//

#include "stdafx.h"
#include "FIT_6204_Gorodilov_TrSeg.h"

#include "FIT_6204_Gorodilov_TrSegDoc.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// CFIT_6204_Gorodilov_TrSegDoc

IMPLEMENT_DYNCREATE(CFIT_6204_Gorodilov_TrSegDoc, CDocument)

BEGIN_MESSAGE_MAP(CFIT_6204_Gorodilov_TrSegDoc, CDocument)
END_MESSAGE_MAP()


// CFIT_6204_Gorodilov_TrSegDoc construction/destruction

CFIT_6204_Gorodilov_TrSegDoc::CFIT_6204_Gorodilov_TrSegDoc()
: m_sScrollSize(400, 400)
, m_bIsFirstPoint(true)
{
	// TODO: add one-time construction code here

}

CFIT_6204_Gorodilov_TrSegDoc::~CFIT_6204_Gorodilov_TrSegDoc()
{
}

BOOL CFIT_6204_Gorodilov_TrSegDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)
	m_aRects.RemoveAll();
	m_bIsFirstPoint = true;

	return TRUE;
}




// CFIT_6204_Gorodilov_TrSegDoc serialization

void CFIT_6204_Gorodilov_TrSegDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		CString buf;
		buf.Format("%d %d\n%d\n", m_sScrollSize.cx, m_sScrollSize.cy, 
			m_aRects.GetCount());
		ar.WriteString(buf);
		INT_PTR count = m_aRects.GetCount();
		for (INT_PTR index = 0; index < count; index++) {
			CFIT_6204_Gorodilov_Rect rectItem = m_aRects.GetAt(index);
			CFIT_6204_Gorodilov_Point &left = rectItem.left();
			CFIT_6204_Gorodilov_Point &right = rectItem.right();
			buf.Format("%d %d %d %d\n", (int)left.x(), (int)left.bottom(), (int)right.x(), (int)right.top());
			ar.WriteString(buf);
		}
	}
	else
	{
		//////////////////////////////////////////////////////////////////////////
		// Scroll size
		CString buf = GetNextLine(ar);	
		int x,y;
		if (sscanf_s(buf, "%d%d",&x, &y) < 2) {
			return;
		}
		m_sScrollSize.cx = x;
		m_sScrollSize.cy = y;
		
		//////////////////////////////////////////////////////////////////////////
		// Rect quantity
		buf = GetNextLine(ar);
		int N;
		if (sscanf_s(buf, "%d",&N) < 1) {
			return;
		}

		//////////////////////////////////////////////////////////////////////////
		// Rects

		int x2, y2;
		for (int i = 0; i < N; i++) {
			buf = GetNextLine(ar);
			if (sscanf_s(buf, "%d%d%d%d", &x, &y, &x2, &y2) < 4) {
				return;
			}
			CFIT_6204_Gorodilov_Rect rect;
			CFIT_6204_Gorodilov_Point& left = rect.left();
			CFIT_6204_Gorodilov_Point& right = rect.right();
			left.x() = x;
			double &tl = left.top();
			double &bl = left.bottom();
			bl = y;
			tl = y2;
			right.x() = x2;
			double &tr = right.top();
			double &br = right.bottom();
			br = y;
			tr = y2;
			m_aRects.Add(rect);
		}
		UpdateAllViews(NULL);
	}
}


// CFIT_6204_Gorodilov_TrSegDoc diagnostics

#ifdef _DEBUG
void CFIT_6204_Gorodilov_TrSegDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CFIT_6204_Gorodilov_TrSegDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG


// CFIT_6204_Gorodilov_TrSegDoc commands
CString GetNextLine(CArchive &ar) {
	CString line = "";
	BOOL isRead = true;
	BOOL isSpace = true;
	while (isSpace && isRead) {
		isSpace = false;
		isRead = ar.ReadString(line);
		line.Trim(" \n\t");
		if (line.IsEmpty()) {
			isSpace = true;
		}
		if (line.GetLength() > 2)
			if ((line[0] == '/') &&
				(line[1] == '/')) {
					isSpace = true;
			}
	}
	return line;
}


const CSize CFIT_6204_Gorodilov_TrSegDoc::GetScrollSize(void) const
{
	return m_sScrollSize;
}

bool CFIT_6204_Gorodilov_TrSegDoc::Run(void)
{	
	INT_PTR count = m_aRects.GetCount();
	CFIT_6204_Gorodilov_Point* points = new CFIT_6204_Gorodilov_Point[count * 2];
	for (INT_PTR index = 0; index < count; index++) {
		CFIT_6204_Gorodilov_Rect rectItem = m_aRects.GetAt(index);
		points[index*2] = rectItem.left();
		points[index*2 + 1] = rectItem.right();
	}

	qsort(points, count*2,
		sizeof(*points), comparePoints);

	CFIT_6204_Gorodilov_TreeElement *head = new CFIT_6204_Gorodilov_TreeElement();
	head->B = 0;
	head->E = m_sScrollSize.cy;
	generateTree(head);
	
	m_aBoundVert.RemoveAll();
	m_aBoundHor.RemoveAll();
	
	CList<CFIT_6204_Gorodilov_Point> stack;	

	long M = 0;
	long P = 0;
	int m0 = 0;
	CFIT_6204_Gorodilov_Point* prevPoint = &points[0];
	for (int i = 0; i < count*2; i++) {
		int m = head->m;
		M = M + m * (int)(points[i].x() - prevPoint->x());
		int a = head->a;
		
		stack.RemoveAll();
		if (points[i].getPointType() == RECT_POINT_LEFT) {
			Contribution(head, points[i], &stack);
			while (!stack.IsEmpty()) {
				m_aBoundVert.Add(stack.RemoveTail());
			}
			AddSegment(head, points[i], 1);
		}

		if (points[i].getPointType() == RECT_POINT_RIGHT) {
			AddSegment(head, points[i], -1);
			Contribution(head, points[i], &stack);
			while (!stack.IsEmpty()) {
				m_aBoundVert.Add(stack.RemoveTail());
			}
		}
		m = head->m;
		P = P + a * (int)(points[i].x() - prevPoint->x()) + abs(m - m0);
		m0 = m;
		prevPoint = &points[i];
	}

	INT_PTR vertCount = m_aBoundVert.GetCount();
	CPoint *p = new CPoint[vertCount * 2];
	for (INT_PTR i = 0; i < vertCount; i++) {
		CFIT_6204_Gorodilov_Point point = m_aBoundVert.GetAt(i);
		p[2*i] = CPoint((int)point.x(), (int)point.top());
		p[2*i + 1] = CPoint((int)point.x(), (int)point.bottom());
	}

	qsort(p, vertCount*2,
		sizeof(*p), comparePoints2);

	for (INT_PTR i = 0; i < vertCount; i++) {
		CFIT_6204_Gorodilov_Point point;
		point.x() = p[2*i].y;
		double &t = point.top();
		double &b = point.bottom();
		t = p[2*i + 1].x;
		b = p[2*i].x;
		m_aBoundHor.Add(point);
	}

	delete[] p;
	deleteTree(head);
	delete[] points;
	return true;
}


int comparePoints(const void *arg1, const void *arg2)  {
	CFIT_6204_Gorodilov_Point *p1 = (CFIT_6204_Gorodilov_Point *)arg1;
	CFIT_6204_Gorodilov_Point *p2 = (CFIT_6204_Gorodilov_Point *)arg2;
	if (p1->x() < p2->x()) {
		return -1;
	} else {
		if (p1->x() == p2->x()) {
			return 0;
		} else {
			return 1;
		}
	}
}
void CFIT_6204_Gorodilov_TrSegDoc::generateTree(CFIT_6204_Gorodilov_TreeElement* v)
{
	ASSERT(v != NULL);
	if (v->E - v->B <= 1) {
		return;
	}

	int m = (v->B + v->E) / 2;
	v->left = new CFIT_6204_Gorodilov_TreeElement();
	v->left->B = v->B;
	v->left->E = m;
	generateTree(v->left);

	v->right = new CFIT_6204_Gorodilov_TreeElement();
	v->right->B = m;
	v->right->E = v->E;
	generateTree(v->right);
}

void CFIT_6204_Gorodilov_TrSegDoc::deleteTree(CFIT_6204_Gorodilov_TreeElement* v)
{
	ASSERT(v != NULL);
	if (v->left)
		deleteTree(v->left);
	if (v->right)
		deleteTree(v->right);
	delete v;
}

void CFIT_6204_Gorodilov_TrSegDoc::AddSegment(CFIT_6204_Gorodilov_TreeElement* v, CFIT_6204_Gorodilov_Point& point, int direction)
{
	if (point.bottom() <= v->B && v->E <= point.top()) {
		v->C += direction;
	} else 	{
		int m = (int)(v->B + v->E) / 2; 
		if (point.bottom() < m) {
			AddSegment(v->left, point, direction);
		}
		if (m < point.top()) {
			AddSegment(v->right, point, direction);
		}
	}

	//////////////////////////////////////////////////////////////////////////
	// Square
	if (v->C) {
		v->m = v->E - v->B;
	} else if (v->left && v->right) {
		v->m = v->left->m + v->right->m;
	} else {
		v->m = 0;
	}

	//////////////////////////////////////////////////////////////////////////
	// Perimeter
	if (v->C > 0) {
		v->a = 2;
		v->isLeft = 1;
		v->isRight = 1;
	} else {
		if (v->left && v->right) {
			v->a = v->left->a + v->right->a - 2 * v->left->isRight * v->right->isLeft;
			v->isLeft = v->left->isLeft;
			v->isRight = v->right->isRight;
		} else {
			v->a = 0;
			v->isLeft = 0;
			v->isRight = 0;
		}
	}

	//////////////////////////////////////////////////////////////////////////
	// Bound
	if (v->C > 0) {
		v->status = 2;
	} else if (!v->left || !v->right) {
		v->status = 0;
	} else if (0 == v->left->status && 0 == v->right->status) {
		v->status = 0;
	} else {
		v->status = 1;
	}
}

void CFIT_6204_Gorodilov_TrSegDoc::RemoveSegment(CFIT_6204_Gorodilov_TreeElement* v, CFIT_6204_Gorodilov_Point& point)
{
	if (point.bottom() <= v->B && v->E <= point.top()) {
		v->C--;
	} else 	{
		int m = (int)(v->B + v->E) / 2; 
		if (point.bottom() < m) {
			RemoveSegment(v->left, point);
		}
		if (m < point.top()) {
			RemoveSegment(v->right, point);
		}
	}
	if (v->C) {
		v->m = v->E - v->B;
	} else if (v->left && v->right) {
		v->m = v->left->m + v->right->m;
	} else {
		v->m = 0;
	}
}


void CFIT_6204_Gorodilov_TrSegDoc::Contribution(CFIT_6204_Gorodilov_TreeElement* v, CFIT_6204_Gorodilov_Point& point, 
				  CList<CFIT_6204_Gorodilov_Point> *stack) 
{
	ASSERT(stack != NULL);
	if (!v) {
		return;
	}
	if (v->status != 2) {
		if (point.bottom() <= v->B && v->E <= point.top() && v->status == 0) {
			if (!stack->IsEmpty() &&
				stack->GetTail().top() == v->B) {
				stack->GetTail().top() = v->E;
			} else {
				CFIT_6204_Gorodilov_Point p;
				double &t = p.top();
				double &b = p.bottom();
				p.x() = point.x();
				b = v->B;
				t = v->E;
				stack->AddTail(p);
			}
		} else {
			int m = (int)(v->B + v->E) / 2; 
			if (point.bottom() < m) {
				Contribution(v->left, point, stack);
			}
			if (m < point.top()) {
				Contribution(v->right, point, stack);
			}
		}
	}
}

int comparePoints2(const void *arg1, const void *arg2)  {
	CPoint *p1 = (CPoint *)arg1;
	CPoint *p2 = (CPoint *)arg2;
	if (p1->y < p2->y) {
		return -1;
	} else {
		if (p1->y == p2->y) {
			if (p1->x < p2->x) {
				return -1;
			} else {
				if (p1->x == p2->x) {
					return 0;
				}
				return 1;
			}
		} else {
			return 1;
		}
	}
}
